#include <iostream>
using namespace std;

void swap(char &a, char &b)
{
	if(&a != &b) //must avoid self swap
		a^=b^=a^=b;
}

int factorial(int n)
{
	static const int PoolMax = 6;
	static const int pool[PoolMax+1] = {1,1,2,6,24,120,720};
	if(n <= PoolMax)
		return pool[n];
	int re = pool[PoolMax];
	for(int i = PoolMax+1; i<=n; i++)
		re *= i;
	return re;
}

void perm(char str[], int l, int h)
{
	if(l == h)
	{
		cout << str << endl;
		return;
	}
	for(int i=l; i<=h; i++)
	{
		swap(str[i], str[l]);
		perm(str, l+1, h);
		swap(str[i], str[l]);
	}
}

void permk(char str[], int l, int h, int k)
{
	if(k==0)
	{
		for(int j=0; j<l; j++)
			cout << str[j];
		cout << endl;
		return;
	}
	for(int i=l; i<=h; i++)
	{
		swap(str[i], str[l]);
		permk(str, l+1, h, k-1);
		swap(str[i], str[l]);
	}
}

void genperm(char str[], int n, int index)
{
	char *s = new char[n+1];
	memcpy(s, str, n);
	s[n] = '\0';
	for(int i=0; i<n-1; i++)
	{
		int g = index / factorial(n-i-1);
		swap(s[i], s[g+i]);
		index = index % factorial(n-i-1);
	}
	cout << s << endl;
	delete s;
}

void comb(char str[], int l, int h, int k, char cb[], int t)
{
	if(k == 0)
  {
		cb[t] = '\0';
		cout << cb << endl;
		return;
	}
	for(int i=l; i<=h-k+1; i++)
	{
		cb[t] = str[i];
		comb(str, i+1, h, k-1, cb, t+1);
	}
}

int main()
{
	char str1[] = {'a','b','c','d','\0'};
	perm(str1, 0, 3);
	cout << "============================" << endl;
	char str2[] = {'a','b','c','d','\0'};
	permk(str2, 0, 3, 2);
	cout << "============================" << endl;
	char str3[] = {'a','b','c','d','\0'};
	for(int i=0; i<factorial(4); i++)
		genperm(str3, 4, i);
	cout << "============================" << endl;
	char str4[] = {'a','b','c','d','\0'};
	char cb[3];
	comb(str4, 0, 3, 2, cb, 0);
	return 0;
}
